package com.hyper_yang.algorithmRecord;

import java.util.Arrays;

// 搜索二维矩阵
public class LeetCode_74 {
    /*
        给你一个满足下述两条属性的 m x n 整数矩阵：
        每行中的整数从左到右按非严格递增顺序排列。
        每行的第一个整数大于前一行的最后一个整数。
        给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
    */
    public static boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        if (target < matrix[0][0] || target > matrix[m][n]) return false;
        for (int[] line : matrix) {
            if (target >= line[0] && target <= line[n]) {
                return binarySearch(line, target);
            }
        }
        return false;
    }

    private static boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (target > arr[mid]) left = mid + 1;
            else if (target == arr[mid]) return true;
            else right = mid - 1;
        }
        return false;
    }

    // 优化:
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;

        int left = 0;
        int right = n * m - 1;

        while (left <= right) {
            int mid = (left + right) >> 1;
            int midElement = matrix[mid / n][mid % n];
            if (target > midElement) left = mid + 1;
            else if (target == midElement) return true;
            else right = mid - 1;
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}};
        System.out.println(searchMatrix(matrix, 3));
        System.out.println(searchMatrix(matrix, 13));
        System.out.println(searchMatrix(new int[][]{{1}}, 1));

    }
}
